The present invention relates to an improved system for correcting errors which can effectively conbined with, for example, a digital audio disk (DAD) device using a compact disk (CD).
Various optical DAD devices have been developed recently. As is well known, an optical DAD device having a CD uses cross interleaved Reed-Solomon codes (CIRC) to correct errors. A CIRC is obtained by submitting a Reed-Solomon code, which is a kind of BCH code and is generally regarded as the most effective random error correction code hitherto known to a signal process called "cross interleaving." The CIRC thus obtained is sensitive enough to correct burst errors.
A Reed-Solomon code can be decoded in the same way as other BCH codes, thereby correcting errors.
A typical Reed-Solomon code consisting of k data symbols and (n-k) inspection symbols, i.e., consisting of n symbols, is decoded in the following manner. Here, n symbols are represented by the 2.sup.m elements of a finite field or a Galois field GF (2.sup.m) which represents m binary bits. The generator polynomil g.sub.(x) representing the Reed-Solomon code used to correct an error a t number of times is given by the following two equations, where .alpha. is the origin element Galois field GF (2.sup.m): EQU g.sub.(x) =(x+.alpha.) (x+.alpha..sup.2), . . . (x+.alpha..sup.2t), (1) EQU g.sub.(x) =(x+.alpha..sup.0) (x+.alpha.), . . . (x+.alpha..sup.2t-1). (2)
If we let C.sub.(x), R.sub.(x) and E.sub.(x) denote a transmitted code word, a received code word and an error polynomial, then: EQU R.sub.(x) =C.sub.(x) +E.sub.(x). (3)
The coefficients contained in polynomial E.sub.(x) are also contained in the Galois field GF (2.sup.m). Hence, the error polynomial E.sub.(x) contains only those terms which correspond to error locations and the value (i.e., size) of the error.
If we let X.sup.j denote an error location, and let Y.sub.j denote the value of the error at the error location X.sup.j, the error polynomial E.sub.(x) can then be given as: ##EQU1## where .SIGMA. is the sum of the errors at all of the error locations.
Here, syndrome S.sub.i is described: EQU S.sub.i =R(.alpha..sup.i) [i=0,1 . . . 2t-1]. (5)
Then, from equation 3 we have: EQU S.sub.i =C(.alpha..sup.i)+E(.alpha..sup.i).
Both C.sub.(x) and g.sub.(x) can be divided without leaving a remainder. As a result, the following therefore holds true: EQU S.sub.i =E(.alpha..sup.i).
From equation 4 it is evident that syndrome S.sub.i may be expressed as follows: ##EQU2## where .alpha..sup.j =X.sub.j, and X.sub.j represents the error location for .alpha..sup.j.
Error location polynomial .sigma..sub.(x) is given by: ##EQU3## where e is the number of the errors.
.sigma..sub.1 to .sigma..sub.e in Equation 7 are related to syndrome S.sub.i as shown below: EQU S.sub.i+e +.sigma..sub.1 S.sub.i+e-1 +. . . .sigma..sub.e-1 S.sub.i+1 +.sigma..sub.e S.sub.i. (8)
To sum up the above, a Reed-Solomon code as defined can be decoded as follows:
(I) Calculate syndrome S.sub.i (Equation 5). PA1 (II) Obtain coefficients .sigma..sub.1 to .sigma..sub.e contained in the error location polynomial .sigma..sub.(x) (Equation 8). PA1 (III) Find the root X.sub.j of the error location polynomial .sigma..sub.(x) (Equation 7). PA1 (IV) Find the error value Y.sub.j (Equation 6) and calculate the error polynomial (Equation 4). PA1 (V) Correct the error (Equation 3). PA1 See Method A. PA1 See Method A.
By using the steps listed above, the steps needed to decode, a Reed-Solomon code consisting of many block data each containing four inspection symbols will be described. This code is represented by the following generator polynomial g.sub.(x) : EQU g.sub.(x) =(x+1) (x+.alpha.) (x+.alpha..sup.2) (x+.alpha..sup.3).
In this case, an error can be corrected twice. The Reed-Solomon code may then be decoded by following method A or by following method B.
[Method A]
(I) Find syndromes S.sub.0 to S.sub.3.
(II) Rewrite Equation 8 so that e equals 1 and 2,
In the case of e=1: EQU S.sub.1 +.sigma..sub.1 S.sub.0 =0, EQU S.sub.2 +.sigma..sub.1 S.sub.1 =0, EQU S.sub.3 +.sigma..sub.1 S.sub.2 =0. (9)
In the case of e=2: EQU S.sub.2 +.sigma..sub.1 S.sub.1 +.sigma..sub.2 S.sub.0 =0, EQU S.sub.3 +.sigma..sub.1 S.sub.2 +.sigma..sub.2 S.sub.1 =0. (10)
Assume that the decoder used starts functioning in the case where e=1. A solution .sigma..sub.1 must then be given which satisfies the simultaneous Equations 9. If no solution .sigma..sub.1 is found, the decoder must find solutions .sigma..sub.1 and .sigma..sub.2 which satisfy simultaneous Equation 10. If a solution .sigma..sub.1 or .sigma..sub.2 is not yet found, then: e.gtoreq.3.
The solution .sigma..sub.1 of Equation 9 can be expressed by: ##EQU4##
The solution .sigma..sub.1 and .sigma..sub.2 of Equation 10 is: ##EQU5##
(III) If a coefficient .sigma..sub.1 in the error location polynomial is obtained, find the root of the error location polynomial (Equation 7).
In the case of e=1: EQU .sigma..sub.(x) =x+.sigma..sub.1 =0. Therefore, X.sub.1 =.sigma..sub.1.
In the case of e=2: EQU .sigma..sub.(X) =x.sup.2 +.sigma..sub.1 x+.sigma.2=0 (11)
Substituting the elements of the Galois field GF (2.sup.m) in Equation 11 one after another will yield roots X.sub.1 and X.sub.2.
(IV) If the roots of the error location polynomial are found, determine the error value Y.sub.j (Equation 6).
In the case of e=1: EQU S.sub.0 =Y.sub.1. Therefore, Y.sub.1 =S.sub.0.
In the case of e=2: EQU S.sub.0 =Y.sub.1 +Y.sub.2, EQU S.sub.1 =Y.sub.1 X.sub.1 +Y.sub.2 X.sub.2.
Therefore: ##EQU6##
(V) Correct the error by using the correction values Y.sub.1 and Y.sub.2 thus obtained.
If the value of an error location is correctly found by the pointer erasure method, the Reed-Solomon code used to correct an error twice can be used to correct an error four times in method B.
[Method B]
(I) Find syndromes S.sub.0 to S.sub.3.
(II), (III) Find the error location by using different methods.
(IV) Find the error value (Equation 6).
In the case of e=1:
In the case of e=2:
In the case of e=3: EQU S.sub.0 =Y.sub.1 +Y.sub.2 +Y.sub.3, EQU S.sub.1 =Y.sub.1 X.sub.1 +Y.sub.2 X.sub.3 +Y.sub.3 X.sub.3, EQU S.sub.2 =Y.sub.1 X.sub.1.sup.2 +Y.sub.2 X.sub.2.sup.2 +Y.sub.3 X.sub.3.sup.2.
Solve these simultaneous equations, thus finding Y.sub.1, Y.sub.2 and Y.sub.3 : ##EQU7##
In the case of e=4: EQU S.sub.0 =Y.sub.1 +Y.sub.2 +Y.sub.3 +Y.sub.4, EQU S.sub.1 =Y.sub.1 X.sub.1 +Y.sub.2 X.sub.2 +Y.sub.3 X.sub.3 +Y.sub.4 X.sub.4, EQU S.sub.2 =Y.sub.1 X.sub.1.sup.2 +Y.sub.2 X.sub.2.sup.2 +Y.sub.3 X.sub.3.sup.2 +Y.sub.4 X.sub.4.sup.2, EQU S.sub.3 =Y.sub.1 X.sub.1.sup.3 +Y.sub.2 X.sub.2.sup.3 +Y.sub.3 X.sub.3.sup.3 +Y.sub.4 X.sub.4.sup.3.
Solve these simulataneous equations, thus finding Y.sub.1, Y.sub.2, Y.sub.3 and Y.sub.4 : ##EQU8##
(V) Correct the error, using correction values Y.sub.1, Y.sub.2, Y.sub.3 and Y.sub.4 thus obtained.
FIG. 1 is a block diagram of a known data correcting system which is designed to decode Reed-Solomon codes in the manner described above. A data to be corrected by a Reed-Solomon code is supplied through an input terminal IN. The data is stored into a data buffer 11 and is kept there until code decoding (described later) is completed. The data is also supplied to a syndrome calculator 12. Using the input data, the calculator 12 calculates syndromes. The syndromes are stored into a syndrome buffer 13.
An OR gate 14 is coupled to the output of the syndrome buffer 13. The OR gate 14 generates two output signals which indicates whether or not an error exists in the syndromes supplied from the syndrome buffer 13. An output signal from the OR gate is supplied to an error location polynomial calculator 15. Upon receipt of the signal, the calculator 15 finds the coefficients in the error location polynomial .sigma..sub.(x). Data representing the coefficients is fed to an error location calculator 16. The error location calculator 16 then finds the root or roots of the error location. Data representing the root or roots is supplied from the calculator 16 to an error value calculator 17. From the input, the calculator 17 calculates the value of the error. The data representing the root or roots, and the data representing the error value are used to correct the data from the data buffer 11.
The calculators 12, 15, 16 and 17 of the data correcting system can detect elements which have a value of "0", and can perform addition, multiplication or division. Of these calculators, the error location polynomial calculator 15 may have the structure shown in FIG. 2 which is disclosed in U.S. Pat. No. 4,142,174.
As shown in FIG. 2, the error location polynomial calculator 16 comprises a syndrome buffer 21, a working buffer 22, a sequence controller 23, a logarithm buffer 24 and an antilogarithm buffer 25. The syndrome buffer 21 is a random-access memory (RAM) for storing a syndrome Si which consists of m-bit data and which represents each element of a Galois field GF (2.sup.m). The working buffer 22 is a RAM for storing the interim result of an algebraic operation performed to find the coefficients of the error location polynomial, and for storing the final result of the operation. The working buffer 22 may store partial results which are used in the operations following the calculation of the coefficients of the error location polynomial. The sequence controller 23 defines the order in which the algebraic operations will be performed. It supplies address signals to the syndrome buffer 21 and the working buffer 22, thereby designating the desired memory locations of these buffers 21 and 22, and thereby checking and branching the results of the algebraic operations which are used in the next algebraic operations. The logarithm buffer 24 is a ROM (read-only memory) and stores a table of the logarithms of the elements of the Galois field GF (2.sup.m). The antilogarithm buffer 25 is also a ROM and stores a table of the antilogarithms of the elements of Galois field GF (2.sup.m).
The address of the logarithm buffer 24 is a binary code of element .alpha..sup.i. Its entry is the logarithm of .alpha. to the base .alpha., that is, i. The entry at address i of the antilogarithm buffer 25 is a binary code of .alpha..sup.i.
Suppose the modulus polynomial F.sub.(x) of the Galois field GF(2.sup.8) is given by: EQU F.sub.(x) =x.sup.8 +x.sup.6 +x.sup.5 +x.sup.4 +1.
Then, the element of the Galois field GF (2.sup.m) other than element 0 can be represented by a linear combination of powers to the root .alpha. of F.sub.(x) =0, or .alpha..sup.0 -.alpha..sup.7, which is expressed as follows: ##EQU9##
In this case, eight coefficients a.sub.0 to a.sub.7 can be used and can be presented as binary vectors. For example, they can be given by: ##EQU10##
The elements of the Galois field GF (2.sup.8) other than the above can be represented as binary vectors.
The addresses (1-255) of the logarithm table are 8-bit binary vectors of elements .alpha..sup.i. Entries corresponding to the addresses are binary notations of the exponent i. In the antilogarithm table, exponent i is used as an address, and the entries are binary vectors of .alpha..sup.i.
Now it will be described how the error location polynomial calculator shown in FIG. 2 performs algebraic operations.
(1) Addition
In order to add element .alpha..sup.i and element .alpha..sup.j, the former supplied from an A register 20 to an exclusive OR gate 27 and the latter is supplied from a B register 26 to the exclusive OR gate 27. An exclusive logic sum of each bit of element .alpha..sup.i and the corresponding bit of element .alpha..sup.j is thus produced. The sum of elements .alpha..sup.i and .alpha..sup.j obtained by the exclusive OR gate 27 is transferred through a C register 19 to the working buffer 22.
(2) Detecting if the Element is 0
In order to detect whether or not element .alpha..sup.i is 0, the element is supplied from the H register 28 to an OR gate 29, which produces a logic sum. The logic sum is transferred via an M register 30 to the working buffer 22. The contents of the M register 30 are 0 only when element .alpha..sup.i is 0.
(3) Multiplication
In order to multiply element .alpha..sup.i by element .alpha..sup.j, it is first detected whether or not these elements are 0. If at least one of these elements is 0, it is obvious that the product will also be 0 and so multiplication is not performed. If neither element is 0, they are loaded into an address register 31 which is connected to the logarithm buffer 24. Outputs i and j from the logarithm buffer 24 are supplied to an adder 34 through a D register 32 and E register 33, respectively. The adder 34 adds a complement of 1, using 2.sup.8 -1 as modulo. The result of this addition, (i+j)=t mod (2.sup.8 -1) is loaded through an L register 35 into an address register 36 which is connected to the antilogarithm buffer 25. If the address input of the antilogarithm buffer 25 is t, the antilogarithm buffer 25 supplies an output .alpha..sup.t. The output .alpha..sup.t is the product of elements .alpha..sup.i and .alpha..sup.j and is transferred to the working buffer 22 through a G register 37.
(4) Division
In order to divide element .alpha..sup.i by element .alpha..sup.j to obtain a quotient .alpha..sup.i /.alpha..sup.j, a method similar to the above-mentioned multiplication is used, but the contents of the E register 33 are subtracted from the contents of the D register 32. More specifically, the logarithm of the element .alpha..sub.j stored in the E register 33 is complemented by a complementer 38. The output data of the complementer 38 is supplied to the complement adder 34 through a F register 39. Thereafter, the data is processed in the same way as when multiplying element .alpha..sup.i by element .alpha..sup.j. In this case, the output from the antilogarithm buffer 25 is the quotient, i.e., the result of the division.
The error location polynomial calculator of the known error correcting system must be provided with a logarithm buffer and an antilogarithm buffer. Without the logarithm buffer and the antilogarithm buffer, the error location polynomial calculator could not perform multiplication or division. Both buffers, which are ROMs, need to have an enormously large memory capacity. This makes it difficult to manufacture the error location polynomial calculator in the form of an LSI. If the calculator may be made into an LSI, the logarithm buffer and the antilogarithm buffer are excluded from the calculator. In this case, the buffers of a large memory capacity have to be connected to the calculator.
If one symbol consists of eight bits and if each buffer stores 255 symbols, the buffer must have a memory capacity of 2040 bits (255.times.8). In this case, the known error location polynomial calculator is provided with two ROMs, the total memory capacity of which amounts to 4080 bits: one ROM storing a table of logarithms and the other ROM storing a table of antilogarithms. However, if the error location polynomial calculator has two ROMs of a large memory capacity, the error correcting system is inevitably complicated and is thus expensive.